Numerical Analysis (CS 450) Spring 2021
What | Where |
---|---|
Time | MW 9:30am-10:45am |
Virtual location | Zoom (see Piazza for link and password) |
Class URL | https://relate.cs.illinois.edu/course/cs450-s21/ |
Class recordings | View MediaSpace » or View ClassTranscribe » |
Web forum | View Piazza » |
Calendar | View Calendar » |
Organization
Course lectures will be done via Zoom (see Piazza for link and password) with recordings posted on ClassTranscribe with captions. Most lectures will include inclass activities, which will not be for credit and can be completed at a later time.
There will be two types of assignments: homeworks and quizzes, with homeworks consisting of coding questions and mathematical derivations, while quizzes will largely consist of multiple choice questions. Quizzes will be worth a relatively small percentage of the overall grade and are intended to review lecture concepts and provide exercise for exams, which will have questions of similar style. Typically there will be two quizzes per week, each consisting of several questions. Homeworks will be assigned on a biweekly basis with breaks for exams (we currently plan to have 5 homeworks). Students enrolled in the 4-credit-hour section will be assigned additional homework questions. Students enrolled in the 3-credit-hour section can complete these for extra credit.
There will be 3 examlets, each 1 hour and 50 minutes long on Feb 24, March 17, and April 7th, as well as a final exam. We will use online proctoring via the computer-based testing facility (CBTF). The examlets will be an hour and 50 minutes long (final exam will be 2 hours and 50 minutes long), and will be available 9:00-10:50, during class-time (but starting half an hour earlier). CBTF automatically offers conflict times at 8:00 am and 8:00 pm the same day (other options may also be available, all conflicts may require approval). You will need to register for each exam via the CBTF scheduler, and can create an account there immediately to receive alerts/reminders. Please also see the CBTF instructions as well information for DRES accomodation.
All homeworks and resources will be posted here. We plan to use Piazza for discussion and announcements.
Exams
The examlet will be accessible at your scheduled CBTF proctored time via the following link.
Homeworks
Homework assignments will be posted below.
Homework 1 » 4-Credit Hour Addendum to Homework 1 »
Homework 2 » 4-Credit Hour Addendum to Homework 2 »
Homework 3 » 4-Credit Hour Addendum to Homework 3 »
Homework 4 » 4-Credit Hour Addendum to Homework 4 »
Quizzes
The latest five quizzes will be posted below. To access all previous quizzes, go to (Participant, View Grades, follow desired flow grade link, follow arrow flow link). Quizzes will be due by the start of the subsequent lecture.
Quiz 21: Extrapolation and Categorization of ODEs »
Quiz 22: Initial Value Problems for Ordinary Differential Equations »
Quiz 23: Methods for Ordinary Differential Equation BVPs »
Quiz 24: Finite Elements and PDEs »
Grading Policies
Course Outline
-
1. Chapter 1: Scientific Computing
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 1: Policies
- Quiz 2: Error, Conditioning, and Floating Point
- Quiz 3: Floating Point Arithmetic
- In-class Activity: Cancellation in Standard Deviation Computation
- Demo: Catastrophic Cancellation
- Demo: Conditioning of Evaluating tan
- Demo: Density of Floating Point Numbers
- Demo: Floating Point and the Series for the Exponential Function
- Demo: Floating Point vs Program Logic
- Demo: Floating point and the Harmonic Series
- Demo: Picking apart a floating point number
- Demo: Polynomial Evaluation Floating Point
- Demo: Truncation vs Rounding
- Demo: Vector Norms
-
2. Chapter 2: Systems of Linear Equations
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 4: Matrix Norms and Condition Number
- Quiz 5: Conditioning of Linear Systems
- Quiz 6: Solving Linear Systems
- In-class Activity: Singular Value Decomposition and Norms
- In-class Activity: Sherman-Morrison-Woodbury Formula
- Demo: Coding back-substitution
- Demo: Complexity of Mat-Mat multiplication and LU
- Demo: Condition number visualized
- Demo: Conditioning of 2x2 Matrices
- Demo: Elimination Matrices I
- Demo: Elimination Matrices II
- Demo: LU factorization
- Demo: LU with Partial Pivoting
- Demo: Matrix norms
- Demo: Sherman-Morrison
- Demo: Vanilla Gaussian Elimination
-
3. Chapter 3: Linear Least Squares
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 7: Least Squares and QR Factorization
- Quiz 8: QR Factorization Algorithms
- Quiz 9: Givens QR and Rank-Deficient Least-Squares
- In-class Activity: Householder QR
- Demo: 3x3 Givens demo
- Demo: 3x3 Householder demo
- Demo: Gram-Schmidt and Modified Gram-Schmidt
- Demo: Gram-Schmidt--The Movie
- Demo: Image compression
- Demo: Interactive Polynomial Fit
- Demo: Issues with the normal equations
- Demo: Keeping track of coefficients in Gram-Schmidt
- Demo: Normal equations vs Pseudoinverse
- Demo: Polynomial fitting with the normal equations
- Demo: Relative cost of matrix factorizations
-
4. Chapter 4: Eigenvalue Problems
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 10: Eigenvalues, Eigenvectors, and their Conditioning
- Quiz 11: Eigenvalue Problems and Basic Iterative Algorithms
- Quiz 12: Computing Many Eigenpairs at Once
- Quiz 13: Krylov Subspace Methods
- In-class Activity: Calculating Eigenpairs of Triangular Matrix
- In-class Activity: Rayleigh Quotient Iteration
- In-class Activity: Computing the Maximum Ritz Value
- In-class Activity: Approximation with Orthogonal Iteration and Lanczos
- Demo: Arnoldi Iteration with Complex Eigenvalues
- Demo: Arnoldi Iteration
- Demo: Arnoldi vs Power Iteration
- Demo: Householder Similarity Transforms
- Demo: Orthogonal Iteration
- Demo: Power iteration and its Variants
- Demo: Rounding in characteristic polynomial using SymPy
-
5. Chapter 5: Nonlinear Equations
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 14: Nonlinear Equations
- Quiz 15: Nonlinear Equations and Optimization
- Demo: Bisection Method
- Demo: Convergence of Newton's Method
- Demo: Convergence of the Secant Method
- Demo: Fixed point iteration
- Demo: Newton's Method
- Demo: Newton's method in n dimensions
- Demo: Rates of Convergence
- Demo: Secant Method
- Demo: Three quadratic functions
-
6. Chapter 6: Optimization
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 15: Nonlinear Equations and Optimization
- Quiz 16: Nonlinear Optimization
- Quiz 17: Gauss-Newton and Constrained Optimization
- Demo: Conjugate Gradient Method
- Demo: Conjugate Gradient Parallel Tangents as Krylov Subspace Method
- Demo: Gauss-Newton
- Demo: Golden Section Proportions
- Demo: Nelder-Mead Method
- Demo: Newton's Method in 1D
- Demo: Newton's Method in n dimensions
- Demo: Sequential Quadratic Programming
- Demo: Steepest Descent
-
7. Chapter 7: Interpolation
- Notes (Michael T. Heath)
- Lecture Notes
- In-class Activity: Monomial Interpolation
- In-class Activity: Chebyshev Interpolation
- Quiz 18: Interpolation
- Quiz 19: Piecewise Interpolation
- Demo: Chebyshev interpolation
- Demo: Choice of Nodes for Polynomial Interpolation
- Demo: Composite Gauss Interpolation Error
- Demo: Interpolation Error
- Demo: Interpolation with Radial Basis Functions
- Demo: Jump with Chebyshev Nodes
- Demo: Monomial interpolation
- Demo: Orthogonal Polynomials
-
8. Chapter 8: Numerical Integration and Differentiation
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 20: Quadrature
- Quiz 21: Extrapolation and Categorization of ODEs
- In-class Activity: Richardson Extrapolation
- Demo: Accuracy of Newton-Cotes
- Demo: Finite Differences vs Noise
- Demo: Floating point vs Finite Differences
- Demo: Gaussian quadrature weight finder
- Demo: Newton-Cotes weight finder
- Demo: Richardson with Finite Differences
- Demo: Taking Derivatives with Vandermonde Matrices
-
9. Chapter 9: Initial Value Problems for ODEs
- Notes (Michael T. Heath)
- Lecture Notes
- In-class Activity: Backward Euler Method
- Quiz 21: Extrapolation and Categorization of ODEs
- Quiz 22: Initial Value Problems for Ordinary Differential Equations
- Quiz 23: Methods for Ordinary Differential Equation BVPs
- Demo: Backward Euler stability
- Demo: Dissipation in Runge-Kutta Methods
- Demo: Forward Euler stability
- Demo: Stability regions
- Demo: Stiffness
- 10. Chapter 10: Boundary Value Problems for ODEs
- 11. Chapter 11: Partial Differential Equations
- 12. Chapter 12: Fast Fourier Transform
- 13. Chapter 13: Random Numbers and Simulation
Team
(Instructor)
Email: solomon2@illinois.edu
Office Hours: Monday 2-3 pm and Wednesday 11-12 pm (link on Piazza)
Lukas Spies
(TA)
Email: lspies@illinois.edu
Office Hours: Tuesday 10-11 am and Thursday 3-4 pm (link on Piazza)
Alexey Voronin
(TA)
Office Hours: Tuesday and Thursday 1-2 pm (link on Piazza)
Shovik Guha
(TA)
Office Hours: Wednesday 1-2 pm and Friday 11-12 pm (link on Piazza)
Textbook
Michael T. Heath, Second Edition, McGraw-Hill.
Available to UIUC students for free by using th UIUC library proxy or VPN via SIAM
Computing
We will be using Python with the libraries numpy, scipy and matplotlib for in-class work and assignments. No other languages are permitted. Python has a very gentle learning curve, so you should feel at home even if you've never done any work in Python.
Virtual Machine Image
While you are free to install Python and Numpy on your own computer to do homework, the only supported way to do so is using the supplied virtual machine image.
Previous Editions of CS 450
Additional Text Resources
- Linear Algebra and Its Applications Gilbert Strang, 4th Edition, Harcourt Brace, 1987 (on reserve at Grainger).
- Numerical Linear Algebra Lloyd Trefethen and David Bau, SIAM, 1997 (on reserve at Grainger).
- Applied Numerical Linear Algebra James Demmel, SIAM, 1997 (on reserve at Grainger).
- Matrix Computations Gene Golub and Charles Van Loan, 4th Edition, The John's Hopkins University Press, 2013.
- Numerical Recipes William Press, Saul Teukolsky, William Vetterling, and Brian Flannery, 3rd Edition, Cambridge University Press, 2007.
Python Help
(see section 1 of the outline for more)
- Python tutorial
- Facts and myths about Python names and values
- Learn Python the hard way
- Project Euler (Lots of practice problems)
Python Workshop Material
- Video: Located on Echo 360 along with the other class recordings
- Tutorial material
- Scipy lecture notes
- CSE workshop training material
Numpy Help
(see section 1 of the outline for more)
- Introduction to Python for Science
- The SciPy lectures
- The Numpy MedKit by Stéfan van der Walt
- The Numpy User Guide by Travis Oliphant
- Numpy/Scipy documentation
- More in this reddit thread
- Spyder (a Python IDE, like Matlab) is installed in the virtual machine. (Applications Menu > Development > Spyder)
- An introduction to Numpy and SciPy